package com.example.question.dp.dp3;

/**
 * @Date 2023-07-30
 * @Author Jonathan
 * @Description 97. 交错字符串  转换为路径问题
 */
public class Code05_97 {


    public boolean isInterleave(String s1, String s2, String s3) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        int m = s1.length();
        int n = s2.length();

        if (m == 0) {
            return s2.equals(s3);
        }
        if (n == 0) {
            return s1.equals(s3);
        }
        if (s3.length() == 0) {
            return false;
        }
        if (m + n != s3.length()) {
            return false;
        }

        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

        for (int i = 1; i <= m; i++) {
            // 当前不是的话 后面的都不是了  就需要break
            if (c1[i - 1] == c3[i - 1]) {
                dp[i][0] = true;
            } else {
                break;
            }
        }


        for (int i = 1; i <= n; i++) {
            // 当前不是的话 后面的都不是了  就需要break
            if (c2[i - 1] == c3[i - 1]) {
                dp[0][i] = true;
            } else {
                break;
            }
        }


        int k;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                k = i + j;
                if (k - 1 < s3.length() && c1[i - 1] == c3[k - 1] && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
                if (k - 1 < s3.length() && c2[j - 1] == c3[k - 1] && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[m][n];
    }
}
